package algorithm;

/**
 * Created by User on 2017/12/1.
 */
public class InsertionSort {

    public static void main(String[] args) {

        int[] ints = new int[]{3,4,5,1,6};


        sort(ints, 0, ints.length - 1);


        print(ints);

        swap();
    }

    public static void print(int[] ints) {
        for (int i : ints) System.out.println(i);
    }

    public static void sort(int[] a, int left, int right) {
        /**
         * 1 2 4 6 中插入3
         * ai=3 a[j]=6 a[j]>ai a[j]=6移动位置  1 2 4 # 6  j 3->2
         * ai=3 a[j]=4 a[j]>ai a[j]=4移动位置  1 2 # 4 6  j 2->1
         * ai=3 a[j]=2 a[j]>ai不成立 a[j+1]=ai 1 2 3 4 6
         */
        // 从小到大排序
        for (int i = left, j = i; i < right; j = ++i) {
            int ai = a[i + 1]; // 当前准备插入数
            while (ai < a[j]) { // 从ai的前一个数开始找  大于ai的话往后移动一个位置
                a[j + 1] = a[j];
                if (j-- == left) {
                    break;
                }
            }
            a[j + 1] = ai;
        }
    }

    public static void sort2(int[] a, int left, int right) {
        /*
         * Skip the longest ascending sequence.
         */
        do {
            if (left >= right) {
                return;
            }
        } while (a[++left] >= a[left - 1]);

        /*
         * Every element from adjoining part plays the role
         * of sentinel, therefore this allows us to avoid the
         * left range check on each iteration. Moreover, we use
         * the more optimized algorithm, so called pair insertion
         * sort, which is faster (in the context of Quicksort)
         * than traditional implementation of insertion sort.
         */
        for (int k = left; ++left <= right; k = ++left) {
            int a1 = a[k], a2 = a[left];

            if (a1 < a2) {
                a2 = a1;
                a1 = a[left];
            }
            while (a1 < a[--k]) {
                a[k + 2] = a[k];
            }
            a[++k + 1] = a1;

            while (a2 < a[--k]) {
                a[k + 1] = a[k];
            }
            a[k + 1] = a2;
        }
        int last = a[right];

        while (last < a[--right]) {
            a[right + 1] = a[right];
        }
        a[right + 1] = last;
    }

    public static void swap() {
        int a = -1123123123, b = 2123213123;

        a ^= b;
        b ^= a;
        a ^= b;

        System.out.println(a + "  " + b);

    }
}
